# Q: Given the value of two nodes in a binary search tree, find the low-est
# common ancestor. You may assume that both values already exist in the tree.
#
# A: One easy way to it is to create the path from the root while walking the
# tree in search each given values. Compare the two generated paths. The last
# common element is the lowest common ancestor. This will take O(2n+h) which is
# still O(n).
#
# Another way is to search the two given values at the same time. While walking
# the tree, as soon as the search can no longer to the same direction, the node
# at which the search is is the lowest common ancester.

from Commons import *
from functools import partial

tree = BinaryTree(8,
            BinaryTree(3,
               BinaryTree(1, None, None),
               BinaryTree(6,
                  BinaryTree(4, None, None),
                  BinaryTree(7, None, None)
                  )
               ),
            BinaryTree(10,
               None,
               BinaryTree(14,
                  BinaryTree(13, None, None),
                  None)
               )
            )


def lowest_common_ancestor(tree, a, b):
   def track_path(p, t):
      p.append(t.value)
      return True

   a_path = []
   find_elem_in_tree(tree, a, partial(track_path, a_path))

   b_path = []
   find_elem_in_tree(tree, b, partial(track_path, b_path))

   answer = list([a for (a,b) in zip(a_path, b_path) if a == b])[-1]
   return answer


print("Lowest Common Ancessor:", lowest_common_ancestor(tree, 3, 6))      




